In a conventional navigation system, routes in a traffic-route network are determined between set starting and destination points using optimization.
For mathematical processing, a traffic-route network is represented as a graph having segments k for road sections and nodes p for traffic junctions. The segments represent the roads, and the nodes represent the interconnection points of the road network. Since the traffic flow is directional in the real road network, a segment is described as a directional vector.
The segments are assigned section resistances. The section resistance represents a parameter for the effort in traveling from one node in the traffic-route network to another node. In the simplest case, the segment length can be directly used as the section resistance. As an alternative, the travel time on a segment can also be regarded as its section resistance, assuming a particular traffic speed (slow, medium, fast). However, optimization methods are also known, in which travel time, length, and other variables are linked each other, in order to calculate the section resistance of a segment in a graph.
It is known in the art that the nodes can each be assigned a maneuvering resistance.
An optimum route from a starting point on a starting segment to a destination point on a destination segment is determined by conventional, best-way route calculation algorithms such a that the sum of all the section resistances assigned to the segments of the optimum route is minimized.
A standard algorithm for route optimization is described in Ford, Moore and explained in detail in the following.
The best-way route optimization algorithm is reverse iterating, with all of the segments in the graph of the traffic-route network between the starting segment and the destination segment being visited and evaluated for the most favorable resistance to the destination segment. Starting out from a destination segment, the route most favorable in terms of resistance to the segments, which are specified in a list and optimized in the previous iteration step, is visited here in each iteration step. As a result, the method supplies the optimum route from each segment in the graph to the destination segment. The calculation results are stored in a route table in which the resistance up to the destination segment and the subsequent successor segment in the destination direction is specified for each segment in the graph of the traffic-route network. The resistance of each segment is set to “infinite” and the successor segment is set to “undefined” as initialization values. In each instance, a resistance and a successor segment in the direction of the corresponding segment is stored for each segment, as well as a resistance and a successor segment in the direction opposite to the resistance.
Prior to the start of the iterative optimization, the destination segment is initialized to have a resistance of zero in the route table. In addition, the destination edge is entered into a final list for segments that are already optimized. A further optimization list is needed for storing the segments to be checked in the next optimization steps. This optimization list is empty at the start of the method.
The optimization method is begun after the initialization, all of the segments specified in the final list being considered imaginary, actual positions of a vehicle. All of the incoming segments interconnected with this actual segment are subjected to an optimization test. For the optimization, it is assumed that the vehicle is situated on one of the incoming segments, with the direction of travel towards the actual segment. As an optimization condition, it is then checked if the resistance of the old, available route of the incoming segment is worse than the resistance for the new route of the incoming segment, using the actual segment. If the route through the actual segment turns out to be more optimal, the optimization is accomplished by entering the corresponding, optimum resistances and successor segments for the respective incoming segments.
The condition for optimizing the resistances may be mathematically represented as follows:RRT, actual segment+Rsegment, incoming segment<RRT-old, INCOMING segment,where RRT, actual segment is the resistance from the route table, of the considered, actual segment to the destination;
Rsegment, incoming segment is the segment resistance of an incoming segment interconnected with the actual segment, and
RRT-old, INCOMING segment is the resistance from the route table, of the incoming segment interconnected with the actual segment, to the destination.
Optimization takes place when the above-mentioned inequality condition is satisfied, i.e., the new resistance of the incoming segment is less than the old resistance of the incoming segment. The resistance of the incoming segment is replaced in the route table with the new, lesser value. The actual segment is entered in as the successor segment, and the optimized, incoming segment is introduced into the final list.
If all of the segments from the optimization list have been processed, as described, then the optimization list and the final list are interchanged. The basis for the next optimizations are the segments optimized here in the last step. The method is terminated when the final list is found to be empty, i.e., when there are no more segments optimized in the previous run.
In conventional navigation systems, a route to be optimized may be influenced by the user, for example, by                choosing different optimization criteria, such as a short route, fast route, or avoidance of expressways, etc.;        controlling road sections manually, or by way of traffic telematics, the road sections then being able to be driven around or favored during the calculation of the optimum route; and        defining one or more intermediate destinations, which are then approached in order, in order to finally lead to a destination.        
Besides defining intermediate destinations, the user has, however, no possibility of presetting a particular section of his route, which necessarily becomes a part of the route between the starting segment and the destination segment. Thus, there is the need, for example, to stipulate a route along tourist streets as a fixed route section, for, in different regions, certain streets are identified as tourist streets, which run along predetermined objects or have other special features. Thus, a wine trail, china street, or avenue, as well as a romantic street, are known, for example, in Germany.
In addition, there is a need to establish external definitions of routes. This is useful, for example, when the user should use particular roads on his way to the destination.
However, the stipulation of a fixed route section to be used should not be completely obligating. In the event of a deviation from the fixed route section, the route calculation unit should lead the driver back to the fixed route section, taking the local conditions into consideration, but it should not lead the driver back by compelling him to turn around (compulsory turning-around).
Conventional navigation systems do not allow route sections to be fixed in advance.
The “TravelPilot DX-N” navigation system allows a user to define a tour, in that the fixed route section is described by intermediate destinations. However, the conventional route-optimization algorithms do not ensure that the fixed route section is universally used. In addition, the route from the current vehicle position to the destination is not calculated in this navigation system.
Therefore, an object of the present invention is to provide an improved method for automatically calculating optimum routes in a traffic-route network, in view of at least one set, fixed route section, where the calculated, optimized route leads through as large a part of the fixed route section as possible and the individual route sections are optimal.